package or;

public class T2654 {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                sum++;
            }
        }
        if (sum > 0) {
            return n - sum;
        }
        int shortLen = n + 1;
        for (int i = 0; i < n; i++) {
            int com = nums[i];
            for (int j = i + 1; j < n || com == 1; j++) {
                com = gcd(com, nums[j]);
                if (com == 1) {
                    shortLen = Math.min(shortLen, j - i + 1);
                    break;
                }
            }
        }
        return shortLen == n + 1 ? -1 : shortLen + n - 2;
    }

    public int gcd(int a, int b) {
        if (a == 1 || b == 1) return 1;
        int c;
        while (a != b) {
            c = Math.abs(a - b);
            a = Math.min(a, b);
            b = c;
        }
        return a;
    }
}
